package _2022.hot100._23_合并K个升序链表;

import java.util.*;

/**
 * @author： YHSimon
 * @date： 2022-04-04 20:09
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {

    //分治合并
    public ListNode mergeKLists3(ListNode[] lists){
        return merge(lists, 0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int l,int r){
        if(l==r){
            return lists[l];
        }
        if(l>r){
            return null;
        }
        int mid=(l+r)/2;
        return mergeTwoLists(merge(lists, l, mid),merge(lists, mid+1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b){
        if(a==null||b==null){
            return a!=null?a:b;
        }
        ListNode preHead = new ListNode(-1);
        ListNode pre=preHead,aCur=a,bCur=b;
        while(aCur!=null&&bCur!=null){
            if(aCur.val<bCur.val){
                pre.next=aCur;
                aCur=aCur.next;
            }else{
                pre.next=bCur;
                bCur=bCur.next;
            }
            pre=pre.next;
        }
        pre.next=aCur!=null?aCur:bCur;
        return preHead.next;
    }

    //优先队列
    public ListNode mergeKLists2(ListNode[] lists){
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for(ListNode node:lists){
            if(node!=null){
                pq.offer(node);
            }
        }
        ListNode preHead=new ListNode(-1);
        ListNode pre=preHead;
        while(!pq.isEmpty()){
            ListNode cur=pq.poll();
            pre.next=cur;
            pre=pre.next;
            if(cur.next!=null){
                pq.offer(cur.next);
            }
        }
        return preHead.next;
    }
    //重构
    public ListNode mergeKLists(ListNode[] lists){
        ListNode preHead=new ListNode(-1);
        ListNode pre=preHead;
        List<Integer> nums = new ArrayList<>();
        for(ListNode node: lists){
            while(node!=null){
                nums.add(node.val);
                node=node.next;
            }
        }
        Collections.sort(nums);
        for(int i:nums){
            pre.next=new ListNode(i);
            pre=pre.next;
        }
        return preHead.next;
    }

    public static void main(String[] args) {
        ListNode[] lists=new ListNode[3];
        ListNode node1 = new ListNode(1, new ListNode(4,new ListNode(5)));
        ListNode node2=new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode node3=new ListNode(2,new ListNode(6));
        lists[0]=node1;
        lists[1]=node2;
        lists[2]=node3;
        Solution s = new Solution();
        ListNode x = s.mergeKLists2(lists);
        while(x!=null){
            System.out.println(x.val);
            x=x.next;
        }
    }
}
